#include "interpolationsearch.h"

// 构造函数：对传入的值排序并初始化查找状态
InterpolationSearch::InterpolationSearch(const QVector<int>& values)
    : low(0), high(values.size() - 1), target(-1),
      found(false), finished(false), foundIndex(-1), compareCount(0)
{
    QVector<int> sortedValues = values;
    std::sort(sortedValues.begin(), sortedValues.end()); // 插值查找需要有序数据
    for (int v : sortedValues)
        bars.append({v, Qt::lightGray}); // 初始化每个条为灰色（未查找状态）
}

// 执行一次插值查找的操作
void InterpolationSearch::step() {
    // 查找结束的条件（索引越界或区间值相同无法估算）
    if (finished || low > high || bars[low].value == bars[high].value) {
        finished = true;
        return;
    }

    // 清除颜色标记
    for (auto& bar : bars)
        bar.color = Qt::lightGray;

    // 根据插值公式估算目标所在位置
    pos = low + (target - bars[low].value) * (high - low) / (bars[high].value - bars[low].value);
    compareCount++;

    // 边界检查
    if (pos < 0 || pos >= bars.size()) {
        finished = true;
        return;
    }

    bars[pos].color = Qt::red; // 当前估算位置标红

    if (bars[pos].value == target) {
        bars[pos].color = Qt::green; // 找到目标元素，标绿
        found = true;
        foundIndex = pos;
        finished = true;
    } else if (bars[pos].value < target) {
        low = pos + 1; // 目标值在右侧
    } else {
        high = pos - 1; // 目标值在左侧
    }
}

// 判断是否完成查找
bool InterpolationSearch::isFinished() const {
    return finished;
}

// 返回当前数据（用于界面可视化显示）
const QVector<SortBar>& InterpolationSearch::getData() const {
    return bars;
}

// 设置要查找的目标值
void InterpolationSearch::setTarget(int value) {
    target = value;
}

// 返回是否成功查找到目标值
bool InterpolationSearch::isFound() const {
    return found;
}

// 获取目标值的索引（若找到）
int InterpolationSearch::getFoundIndex() const {
    return foundIndex;
}

// 返回插值查找的简要文字说明
QString InterpolationSearch::getDescription() const {
    return "插值查找：基于值估算目标位置，更适用于数据均匀分布的数组。";
}

// 获取并清空当前步的比较次数
int InterpolationSearch::getAndResetCompareCount() {
    int c = compareCount;
    compareCount = 0;
    return c;
}
